import java.util.*;

/**
 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
 *
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-search-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class WorldFind {

    static int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};

    public static List<String> findWords(char[][] board, String[] words) {
        Trie trie=new Trie();
        for (int i = 0; i <words.length ; i++) {
            trie.insert(words[i]);
        }
        Set<String> ans=new HashSet<String>();
        for (int i = 0; i <board.length ; i++) {
            for(int j=0;j<board[0].length;j++){
                dfs(board,trie,i,j,ans);
            }
        }
        return new ArrayList<String>(ans);
    }

    public static void dfs(char[][] board, Trie trie, int i1, int j1, Set<String> ans) {
        char h=board[i1][j1];
        if(!trie.child.containsKey(board[i1][j1])){
            return;
        }
         trie = trie.child.get(h);
        if(!"".equals(trie.world)){
            ans.add(trie.world);
        }
        board[i1][j1]='#';
        for(int[] dir:dirs){
            int i2=i1+dir[0];
            int j2=j1+dir[1];
            if(i2>=0&&i2<board.length&&j2>=0&&j2<board[0].length){
                dfs(board,trie,i2,j2,ans);
            }
        }
        board[i1][j1]=h;
    }

    public static void main(String[] args) {
        char[][] board = {{'o','a','b','n'},{'o','t','a','e'},{'a','h','k','r'},{'a','f','l','v'}};
        String[] words = {"oa","oaa"};
        System.out.println(findWords(board,words));
    }
}

class Trie{

    public String world;
    public Map<Character,Trie> child;
    boolean isWorld;

    public Trie(){
        this.world="";
        this.child=new HashMap<Character, Trie>();
    }

    public void insert(String world){
        Trie trie=this;
        for (int i = 0; i <world.length() ; i++) {
            char c=world.charAt(i);
            if(!trie.child.containsKey(c)){
                trie.child.put(c,new Trie());
            }
            trie=trie.child.get(c);
        }
        trie.world=world;
    }
}


